public class BinarySearchTree{

    //定义内部类 树节点
    static class TreeNode{

        //定义字段 val、左右孩子节点的引用
        public int val;
        public TreeNode left;
        public TreeNode right;

        //定义含参构造方法
        public TreeNode(int val){
            this.val=val;
        }
    }

    //定义字段 根节点并赋初值null
    public TreeNode root=null;

    //二叉搜索树查找方法
    public TreeNode search(int key){

        //迭代查找
        TreeNode cur = root;
        while (cur != null){
            if(cur.val<key){
                cur=cur.right;
            } else if(cur.val>key){
                cur=cur.left;
            }else{
                return cur;
            }
        }
        return null;
    }

    //二叉搜索树插入方法
    public void insert(int val){

        //利用节点的构造方法创建一个新的节点
        TreeNode node=new TreeNode(val);
        if(root==null){
            root=node;
            return;
        }

        //创建cur（指向当前节点）和pre（指向前驱节点）两个引用，若只创建一个引用则无法确定插入位置的父亲节点
        TreeNode cur=root;
        TreeNode pre=null;

        //迭代找到最终插入位置
        while(cur!=null){
            if(cur.val<val){

                //引用向右下方移动
                pre=cur;
                cur=cur.right;
            }else if(cur.val>val){

                //引用向左下方移动
                pre=cur;
                cur=cur.left;
            }else{

                //二叉搜索树中有同值节点，直接返回
                return;
            }

            //此时pre指向的节点就是待插入位置的父亲节点，判断大小从而确定最终插入位置
            if(pre.val>val){
                pre.left=node;
            }else{
                pre.right=node;
            }
        }
    }

    //二叉树删除方法
    public void remove(int key){
        TreeNode pre=null;
        TreeNode cur=root;
        while(cur!=null) {
            if(cur.val<key){
                pre=cur;
                cur=cur.right;
            }else if(cur.val>key){
                pre=cur;
                cur=cur.left;
            }else{

                //使用删除节点的方法
                removeNode(pre,cur);
                return;
            }
        }
    }

    //删除节点方法（供删除方法使用）
    private void removeNode(TreeNode pre,TreeNode cur) {

        //第一种大情景，cur左边为空
        if (cur.left == null) {

            //第一种小情景，cur本身为root节点
            if (cur == root) {
                root = cur.right;

                //第二种小情景,cur不为root节点且为pre的左节点
            } else if (cur == pre.left) {
                pre.left = cur.right;

                //第三种小情景，cur不为root节点且为pre的右节点
            } else {
                pre.right = cur.right;
            }
        }

        //第二种大情景，cur右边为空
        else if (cur.right == null) {


            //第一种小情景，cur本身为root节点
            if (cur == root) {
                root = cur.left;

                //第二种小情景,cur不为root节点且为pre的左节点
            } else if (cur == pre.left) {
                pre.left = cur.left;

                //第三种小情景，cur不为root节点且为pre的右节点
            } else {
                pre.right = cur.left;
            }

            //第三种大情景，cur左右都不为空
        } else {

            //采用替换策略，寻找cur右子树中最小的节点即目标节点替换删除节点
            //定义目标节点引用及其前驱节点引用
            TreeNode target = cur.right;
            TreeNode targetpre = cur;

            //寻找目标节点
            while (target.left != null) {
                targetpre = target;
                target = target.left;
            }

            //将目标节点的值替换给删除节点
            cur.val = target.val;

            //分目标节点位于前驱节点左右两种情况删除已经被替换过的目标节点
            if (target == targetpre.left) {
                targetpre.left = target.right;
            } else {
                targetpre.right = target.right;
            }

            //同理当然也可以寻找左子树中最大的节点作为目标节点替换删除节点。以下以注释给出：
            /*
            TreeNode target = cur.left;
            TreeNode targetpre = cur;
            while (target.right != null) {
                targetpre = target;
                target = target.right;
            }
            cur.val = target.val;
            if (target == targetpre.right) {
                targetpre.right = target.left;
            } else {
                targetpre.left = target.left;
            }
             */
        }
    }
}
